/*
 * @Author: _LJP 2634716776@qq.com
 * @Date: 2024-01-28 14:53:08
 * @LastEditors: _LJP 2634716776@qq.com
 * @LastEditTime: 2024-01-29 17:07:15
 * @FilePath: /my_-linux/Pro24/Hashi/HashiTable/HashiTabble.hpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#pragma once

//***************************************
//**********闭散列哈希表的实现***********
//***************************************

#include<iostream>
#include<vector>

enum State{
  //设置枚举类型
  /*
    分别为
    1.空
    2.存在
    3.删除
    三个状态
  */
    EMPTY,
    EXIST,
    DELETE
};

template<class K,class V>
struct HashiData{
      //设置节点
        std::pair<K, V> _kv;//Key Value模型
        State _state = EMPTY;//默认情况下节点为空
};

template<class K, class V>
class HashiTable{
    //整体模型
    public:
     typedef HashiData<K, V> Data;//使用typedef进行重命名方便后序的调用

    HashiTable():_tables(0),_n(0){}//构造函数使得初始的Vector容器的大小为0，_n表示当前存在的有效数据

     bool Insert(const std::pair<K, const V> &kv) {

        Data *to_find = Find(kv.first);
        if(to_find) return false; 

        //方法2: 在函数中再次创建一个哈希用来重新插入
        if(_tables.size() == 0 || (_n*100) / _tables.size() >=75){
          /*
            哈希表中存在一个概念为复杂因子
            复杂因子即为数据中存在的数据/表的大小 复杂因子越大时越容易造成哈希冲突 [ps:哈希冲突指的是一个值占了另一个值的位置]

            当复杂因子到达一定大小时需要扩大表的大小从而降低复杂因子
            当然复杂因子不是越小越好: 
            复杂因子太大则 哈希冲突概率高 空间使用率低
            复杂因子太低则 哈希冲突概率低 空间利用率低 

            开空间时不能直接在原地开空间,若是使用在原地开空间则将会破坏原来的哈希规则 使得在查找以及下次插入时都存在问题

            开空间时应该重新开辟一块空间 并且以新的表的大小来确定新的哈希规则重新对数据进行插入 
            同时新的哈希规则制定完毕以后 旧的哈希规则则可以摒弃遗忘 对应的空间也应该释放
            (因为闭散列中使用的哈希结构只采用了vector容器,故不需要再节点中指定对应的析构函数)
          */
          size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
          HashiTable<K, V> newtables;
          newtables._tables.resize(newsize);
          for(auto &it : _tables){
            newtables.Insert(it._kv);
          }
        _tables.swap(newtables._tables);
          /*
          方法1:缺点过于冗余
          size_t newsize = _tables.size()==0 ? 10 : _tables.size()*2;
          std::vector<Data> newtables(newsize);
          for(auto &it : _tables){
              if(it._state == EXIST){
                  //插入
                  size_t hashi = kv.first % newtables.size();
                  size_t index = hashi;
                  size_t i = 0;
                  while (newtables[index]._state == EXIST) {
                    index = (hashi + i) % newtables.size();
                    ++ i;
                  }

                  newtables[index]._kv = it._kv;
                  newtables[index]._state = EXIST;
              }
          }
          _tables.swap(newtables);
          */
           
        }


      //哈希表闭散列的插入思路
      /*
        插入思路为:
        创建一个大小差不多的数组,每个数据%模去哈希表的大小;
        并放在对应的位置当中,若是当前位置存在数据,则使用线性探测或者二次探测的思路将这个数据向后进行存放
            ps:线性探测 探测原本需要插入的位置的下一个位置是否为空,若是为空则把数据进行插入,若是不为空则继续向后探测
      */
       size_t hashi = kv.first % _tables.size();
       size_t index = hashi;
       size_t i = 0;
    //    if (_tables[index]._kv.first == kv.first) return false;
       while (_tables[index]._state == EXIST) {
        
         index = (hashi + i)%_tables.size();
         ++i;
       }

       _tables[index]._kv = kv;
       _tables[index]._state = EXIST;
       ++_n;

       return true;
        }

        Data* Find(const K& key){
          //与插入函数的逻辑相同
          
          if(_tables.size() == 0){
            //如果是空表则返不进行查找
            return nullptr;
          }

          size_t hashi = key % _tables.size();
          size_t index = hashi;
          size_t i = 0;
          while (_tables[index]._state != EMPTY) {  //如果不为空则循环继续找数据

            if (_tables[index]._state == EXIST &&//条件为数据存在在表中且状态为存在
             _tables[index]._kv.first == key)
              return &_tables[index];

            index = (hashi + i) % _tables.size();
            ++i;
            if(index == hashi) break;
            //在查找过程中如果没找到数据的前提下index又回到了hashi的位置则代表已经找了一圈了 说明不存在数据 可以跳出循环(极端情况)
          }
          return nullptr;
        }

        bool Erase(const K& key){
          //采用伪删除法
          /*
            伪删除法的思路只要改变节点中的状态即可
          */
          Data *to_del = Find(key);
           if (to_del) {
            to_del->_state = DELETE;
            --_n;
            return true;
           }
          return false;
        }

        void Check() {
            //测试函数
          for (auto &it : _tables) {
            std::cout << it._kv.first << " : " << it._kv.second << "  state : " << it._state <<std::endl;
          }
        }

    protected:
       

    private:
        std::vector<Data> _tables;//利用vector容器实现闭散列的哈希表
        size_t _n;//存储数据个数
};